package onlinebanking.math;

import java.math.BigInteger;

import java.security.SecureRandom;

/**
 * * @author Edgar
 * 
 */
public class GoldwasserMicali {

	private SecureRandom secureRandom;

	public GoldwasserMicali() {
		this.secureRandom = new SecureRandom();
	}

	public BigInteger findPseudosquare(BigInteger p, BigInteger q) {
		BigInteger pseudoSquare;

		while (true) {
			pseudoSquare = new BigInteger(
					Math.max(p.bitLength(), q.bitLength()), this.secureRandom);

			int lP = legendre(pseudoSquare, p);
			int lQ = legendre(pseudoSquare, q);
			if (lP == -1 && lQ == -1) {
				break;
			}
		}
		return pseudoSquare;
	}

	public int legendre(BigInteger a, BigInteger modulus) {
		BigInteger exponent = modulus.subtract(BigInteger.ONE).divide(
				BigInteger.valueOf(2));

		BigInteger remainder = a.modPow(exponent, modulus);
		if (remainder.compareTo(BigInteger.ONE) == 0
				|| remainder.compareTo(BigInteger.ZERO) == 0) {
			return 1;
		} else {
			return -1;
		}
	}

}
